Quiz #2

1. (2 puntos) Describa el lenguaje representado por la siguiente expresión regular:
   ((

   Esta expresión regular fue usada como ejemplo en clases. El lenguaje regular descrito es: Cadenas sobre el alfabeto Σ={0,1} que comienzan por 0 y terminan en 0.

   
   

2. (3 puntos) La expresión regular:

   (r){m,n}

   reconoce de m a n ocurrencias del patrón r. Por ejemplo, la expresión regular:

   a{1,5}

   concuerda con una cadena de uno a cinco símbolos "a".
   Demuéstrese que para toda expresión regular que contenga operadores de repetición como el descrito existe una expresión regular equivalente sin dichos operadores.
   

   La equivalencia de estas expresiones fue explicada en clase y aparece en las notas docentes que están en este sitio web (r){m,n}=(r)m|(r)m+1|...|(r)n-1|(r)n

   
   

3. (5 puntos) Escriba una definición regular para el siguiente lenguaje:

   Todas las cadenas de símbolos 0 y 1 con un número par de dígitos 0 y un número par de dígitos 1.

   La mejor respuesta fue la dada por el estudiante Tomás Enriquez:

   (((01|10)(01|10))|(00|11))*

   una versión más sencilla: es:

   ((01|10)(01|10)|00|11)*

   El criterio de evaluación fue:

4. 0 puntos si no es una expresión regular
5. 2 puntos si es una expresión regular que se aproxima a la respuesta pero concuerda con cadenas que no pertenecen al lenguaje regular
6. 3 puntos si la expresión regular concuerda con un subconjunto del lenguaje regular, pero no con cadenas que no pertenecen al lenguaje
7. 4 puntos si la expresión regular cumple con lo anterior y además concuerda con casi todo el lenguaje
8. 5 puntos para respuestas correctas, sin importar la complejidad de la expresión regular